Sequences and Summations
Sets are unordered collection of elements S = { a , b , ⋯ } S=\{a, b,\cdots\} S = { a , b , ⋯ }
Sequences are ordered lists of elements
prf:definition **Sequences**
A **Sequence** is a function from a subset of the set of integers\
We use notation $a_n$ to denote the image of the integer $n$\
We call $a_n$ a **term** of the sequence
{bdg-success}`Formal Definition`
Let $S \subseteq \mathbb{Z}$ and suppose $S$ has a least element\
A sequence of numbers is the range of a function\
$f: S \rightarrow\text{ some number set}$
S S S is usually taken to be a set of the form { k , k + 1 , k + 2 , ⋯ } ⊆ Z \{k, k+1, k+2, \cdots\} \subseteq \mathbb{Z} { k , k + 1 , k + 2 , ⋯ } ⊆ Z
Here k = initial index (usually 0,1 ) k\text{ = initial index (usually 0,1 )} k = initial index (usually 0,1 )
The set of numbers is most often R = real numbers \mathbb{R}=\text{ real numbers} R = real numbers
a sequence then is r a n g e ( f ) = { f ( k ) , f ( k + 1 ) , f ( k + 2 ) , ⋯ } range(f)=\{f(k), f(k+1), f(k+2), \cdots\} r an g e ( f ) = { f ( k ) , f ( k + 1 ) , f ( k + 2 ) , ⋯ }
We usually wite a x = f ( n ) a_{x}=f(n) a x = f ( n ) for n ⩾ k n \geqslant k n ⩾ k and r a n g e ( f ) = { a k , a k + 1 , ⋯ , a n , ⋯ } = { a n } n = k N range(f)=\left\{a_{k}, a_{k+1}, \cdots, a_{n}, \cdots\right\}=\left\{a_{n}\right\}_{n=k}^{N} r an g e ( f ) = { a k , a k + 1 , ⋯ , a n , ⋯ } = { a n } n = k N a n a_{n} a n is called the general term
( N ∈ Z (N \in Z ( N ∈ Z or N = + ∞ ) N=+\infty) N = + ∞ ) general term
S = index set S=\text{ index set} S = index set
If S S S is a finite subset of Z \mathbb{Z} Z , then the sequence r a n g e ( f ) range(f) r an g e ( f ) is a finite sequence
If S S S is an infinite subset of Z \mathbb{Z} Z , then the resulting sequence is is an infinite sequence
There are some special sequences that often arise...
Geometric Progression
Here S = { 0 , 1 , 2 , ⋯ } = Z + ∪ { 0 } S=\{0,1,2, \cdots\}=\mathbb{Z}^{+} \cup\{0\} S = { 0 , 1 , 2 , ⋯ } = Z + ∪ { 0 }
and f ( n ) = a n = a r n w h e r e a , r ∈ R f(n)=a_{n}=a r^{n}\quad where\quad a,r\in\mathbb{R} f ( n ) = a n = a r n w h ere a , r ∈ R
The sequence is
{ a n } n = 0 + ∞ = { a , a ⋅ r , a ⋅ r 2 , a ⋅ r 3 , a ⋅ r 4 , ⋯ , a ⋅ r n , ⋯ }
\left\{a_{n}\right\}_{n=0}^{+\infty}=\left\{a, a \cdot r, a \cdot r^{2}, a \cdot r^{3}, a \cdot r^{4}, \cdots, a \cdot r^{n}, \cdots\right\}
{ a n } n = 0 + ∞ = { a , a ⋅ r , a ⋅ r 2 , a ⋅ r 3 , a ⋅ r 4 , ⋯ , a ⋅ r n , ⋯ } a a a is called the initial term and r r r is called the common ratio
prf:definition **Geometric Progression**
This is a sequence of the form
$ a, ar, ar^2, \cdots , ar^n, \cdots $
```{prf:remark} Analogue to exponential functions
A geometric progression is a discrete analogue of the exponential function $f(x)=ar^x$
```
Geometric Series (Finite)
G_{n}&=a+a r+\cdots+a r^{n}\\
&=\sum_{k=0}^{n} a r^{k}= \begin{cases}\displaystyle{\frac{a\left(r^{n+1}-1\right)}{r-1}} &, r \neq 1 \\ (n+1)a &, r=1\end{cases}
Poof Case i) r = 1 r=1 r = 1 .
G n = ∑ k = 0 n a ( 1 ) k = ∑ k = 0 n a ( 1 ) = a ∑ k = 0 n ( 1 ) = a ( 1 + 1 + ⋯ + 1 ⏟ n + 1 terms = a ( n + 1 ) .
\begin{aligned}
G_{n}=\sum_{k=0}^{n} a(1)^{k}=\sum_{k=0}^{n} a(1)=a \sum_{k=0}^{n}(1) & =a(\underbrace{1+1+\cdots+1}_{n+1} \text { terms } \\
& =a(n+1) .
\end{aligned}
G n = k = 0 ∑ n a ( 1 ) k = k = 0 ∑ n a ( 1 ) = a k = 0 ∑ n ( 1 ) = a ( n + 1 1 + 1 + ⋯ + 1 terms = a ( n + 1 ) . Case ii) r ≠ 1 r \neq 1 r = 1
G n = a + a r + a r 2 + ⋯ + a r n r G n = a r + a r 2 + ⋯ + a r n + a r n + 1 ∴ r G n − G n = ( r − 1 ) G n = a r n + 1 − a = a ( r n + 1 − 1 ) . thus G n = a ( r n + 1 − 1 ) r − 1
\begin{aligned}
& G_{n}=a+a r+a r^{2}+\cdots+a r^{n} \\
& r G_{n}=a r+a r^{2}+\cdots+a r^{n}+a r^{n+1} \\
& \therefore r G_{n}-G_{n}=(r-1) G_{n}=a r^{n+1}-a=a\left(r^{n+1}-1\right) \text {. } \\
& \text { thus } G_{n}=\frac{a\left(r^{n+1}-1\right)}{r-1}
\end{aligned}
G n = a + a r + a r 2 + ⋯ + a r n r G n = a r + a r 2 + ⋯ + a r n + a r n + 1 ∴ r G n − G n = ( r − 1 ) G n = a r n + 1 − a = a ( r n + 1 − 1 ) . thus G n = r − 1 a ( r n + 1 − 1 )
prf:Theorem Geometric Sequences in General
If $a$ and $r$ are real numbers and $r\ne 0$, then
$$
\displaystyle\sum^n_{j=0}ar^j = \begin{cases}
\displaystyle\frac{ar^{n+1}-a}{r-1}\quad &if\quad r\ne 1\\
\displaystyle(n+1)a\quad &if\quad r= 1\\
\end{cases}
$$
bdg-secondary proof
Let\qquad S_n&=\sum^n_{j=m}ar^j\\
To compute S S S , first multiply both sides of the equality by r r r and then manipulate the resulting sum as follows:
rS_n&=r\sum^n_{j=0}ar^j\qquad\textcolor{hotpink}{\textrm{multiply both sides by $r$}}\\
&=\sum^n_{j=0}ar^{j+1}\qquad\textcolor{hotpink}{\textrm{by the distributive property}}\\
&=\sum^{n+1}_{k=1}ar^{k}\qquad\textcolor{hotpink}{\textrm{Shifting the index by $k=j+1$}}\\
&=ar^1 + ar^2 + ar^3 + , \cdots , ar^n + ar^{n+1}\\
&=\left(\sum^{n+1}_{k=1}ar^{k}\right)+(ar^{n+1}-a)\qquad\textcolor{hotpink}{\textrm{Isolate $n+1$ term but add $k=0$ term}}\\
&=S_n+(ar^{n+1}-a)\qquad\textcolor{hotpink}{\textrm{Substitute back S for the summation formula}}\\
We see thus that r S n = S n + ( a r n + 1 − a ) rS_n = S_n + (ar^{n+1}-a) r S n = S n + ( a r n + 1 − a ) so solving for S n S_n S n if r ≠ 1 r\ne 1 r = 1 , then
S n = a r n + 1 − a r − 1 \displaystyle S_n = \frac{ar^{n+1} - a}{r - 1} S n = r − 1 a r n + 1 − a
For r = 1 r=1 r = 1 then the S n = ∑ j = 0 n a r j = ∑ j = 0 n a S_n=\sum^n_{j=0}ar^j=\sum_{j=0}^na S n = ∑ j = 0 n a r j = ∑ j = 0 n a
Arithmetic Progression
Here S = { 0 , 1 , 2 , … } = Z + ∪ { 0 } S=\{0,1,2, \ldots\}=\mathbb{Z}^+ \cup\{0\} S = { 0 , 1 , 2 , … } = Z + ∪ { 0 }
and f ( n ) = a + n ⋅ d f(n)=a+n \cdot d f ( n ) = a + n ⋅ d
where a , d ∈ R a, d \in \mathbb{R} a , d ∈ R
the sequence is
{ a n } n = 0 + ∞ = { a , a + d , a + 2 d , ⋯ , a + n d , ⋯ }
\left\{a_{n}\right\}_{n=0}^{+\infty}=\{a, a+d, a+2 d, \cdots, a+n d, \cdots\}
{ a n } n = 0 + ∞ = { a , a + d , a + 2 d , ⋯ , a + n d , ⋯ } a is called the initial term and d d d is called the common difference
prf:definition **Arithmetic Progression**
This is a sequence of the form
$ a, a + d, a + 2d, \cdots , a + nd, \cdots$\
where the *initial term* $a$ and the *common difference* $d$ are *real numbers*
```{prf:remark} Analogue to linear functions
A arithmetic progression is a discrete analogue of the linear function $f(x)=dx + a$
```
Sequences of the form a 1 , a 2 , . . . , a n a_1, a_2, ... , a_n a 1 , a 2 , ... , a n are often used in computer science where these finite sequences are called strings denoted by a 1 a 2 . . . a n a_1 a_2 ... a_n a 1 a 2 ... a n The length of a string is the number of terms in this string the empty string is denoted by λ \lambda λ which of course has no terms and hence has length zero
A n = ∑ k = 0 n ( a + d k ) = ( n + 1 ) ( 2 a + n d ) 2
A_{n}=\sum_{k=0}^{n}(a+d k)=\frac{(n+1)(2 a+n d)}{2}
A n = k = 0 ∑ n ( a + d k ) = 2 ( n + 1 ) ( 2 a + n d ) Poof
A n = ∑ k = 0 n ( a + d k ) = ∑ k = 0 n a + ∑ k = 0 n d k = a ∑ k = 0 n i + d ∑ k = 1 n k = ( n + 1 ) a + d ( ∑ k = 1 n k )
\begin{aligned}
A_{n} & =\sum_{k=0}^{n}(a+d k)=\sum_{k=0}^{n} a+\sum_{k=0}^{n} d k \\
& =a \sum_{k=0}^{n} i+d \sum_{k=1}^{n} k \\
& =(n+1) a+d\left(\sum_{k=1}^{n} k\right)
\end{aligned}
A n = k = 0 ∑ n ( a + d k ) = k = 0 ∑ n a + k = 0 ∑ n d k = a k = 0 ∑ n i + d k = 1 ∑ n k = ( n + 1 ) a + d ( k = 1 ∑ n k ) Fact
∑ k = 1 n k = 1 + 2 + ⋯ + n = n ( n + 1 ) 2
\sum_{k=1}^{n} k=1+2+\cdots+n=\frac{n(n+1)}{2}
k = 1 ∑ n k = 1 + 2 + ⋯ + n = 2 n ( n + 1 ) Thus
A n = ( n + 1 ) a + d n ( n + 1 ) 2 = ( n + 1 ) ( 2 a + n d ) 2
\begin{aligned}
A_{n} & =(n+1) a+d \frac{n(n+1)}{2} \\
& =\frac{(n+1)(2 a+n d)}{2}
\end{aligned}
A n = ( n + 1 ) a + d 2 n ( n + 1 ) = 2 ( n + 1 ) ( 2 a + n d ) Harmonic Progression
Here S = { 1 , 2 , ⋯ } = Z + S=\{1, 2, \cdots\}=\mathbb{Z}^+ S = { 1 , 2 , ⋯ } = Z + and f ( n ) = 1 n f(n)=\frac{1}{n} f ( n ) = n 1
The sequence is
{ a n } n = 1 ∞ = { 1 , 1 2 , 1 3 , ⋯ , 1 n , ⋯ }
\left\{a_{n}\right\}_{n=1}^{\infty}=\left\{1, \frac{1}{2}, \frac{1}{3}, \cdots, \frac{1}{n}, \cdots\right\}
{ a n } n = 1 ∞ = { 1 , 2 1 , 3 1 , ⋯ , n 1 , ⋯ }
prf:example **Harmonic Set**
Consider the sequence $a_n$, where $a_n=1/n$\
The list of the of this sequence, beginning with $a_1$, namely\
$a_1, a_2, a_3, a_4,\cdots,$
$$
1,\frac{1}{2},\frac{1}{3},\frac{1}{4},\cdots,
$$
Recurrence Relation
Before we specified sequences by providing explicit formulas for their terms
but there are other ways to specify a sequence
prf:definition **Recurrence Relation**
A **recurrence relation** for the sequence $\Set{a+n}$ is an equation that expresses $a_n$ in terms of one or more of the previous terms of the sequences, namely for all integers $n\ge n_0$ where $n_0$ is a nonnegative integer.
> A sequence is called a **solution** of a recurrence relation if its terms satisfy the recurrence relation
Some useful Sequences
Summations
a m , a ( m + 1 ) , ⋯ , a n a_m,a_(m+1),\cdots ,a_n a m , a ( m + 1 ) , ⋯ , a n , from the sequence \Set a n \Set{a_n} \Set a n
We use the notation
∑ j = m n a j = ∑ j = m n a j = ∑ m ≤ j ≤ n n a j
\displaystyle\sum^n_{j=m}a_j = \textstyle\sum^n_{j=m}a_j = \displaystyle\sum^n_{m\ \le j\ \le\ n}a_j
j = m ∑ n a j = ∑ j = m n a j = m ≤ j ≤ n ∑ n a j reads as the sum from j = m to j = n of a j \textit{sum from j = m to j = n of }a_j sum from j = m to j = n of a j
Variable j j j is called the index of summation or dummy index you can define it as any variable as below shows
∑ j = m n a j = ∑ i = m n a i = ∑ k = m n a k
\sum^n_{j=m}a_j = \sum^n_{i=m}a_i = \sum^n_{k=m}a_k
j = m ∑ n a j = i = m ∑ n a i = k = m ∑ n a k Variable m m m is called the lower limit or the initial index
Variable n n n is called the upper limit or terminal index
Sum
Closed Form
∑ k = 0 n a r k ( r ≠ 0 ) \displaystyle{\sum^n_{k=0}ar^k\ (r\ne 0)} k = 0 ∑ n a r k ( r = 0 ) ref proof
a r n + 1 − a r − 1 \displaystyle{\frac{ar_{n+1}-a}{r-1}} r − 1 a r n + 1 − a
∑ k = 1 n k \displaystyle{\sum^n_{k=1}k} k = 1 ∑ n k
n ( n + 1 ) 2 \displaystyle{\frac{n(n+1)}{2}} 2 n ( n + 1 )
∑ k = 2 n k 2 \displaystyle{\sum^n_{k=2}k^2} k = 2 ∑ n k 2
n ( n + 1 ) ( 2 n + 1 ) 6 \displaystyle{\frac{n(n+1)(2n+1)}{6}} 6 n ( n + 1 ) ( 2 n + 1 )
∑ k = 2 n k 3 \displaystyle{\sum^n_{k=2}k^3} k = 2 ∑ n k 3
n 2 ( n + 1 ) 2 4 \displaystyle{\frac{n^2(n+1)^2}{4}} 4 n 2 ( n + 1 ) 2
∑ k = 0 ∞ x k , ∣ x ∣ < 1 \displaystyle{\sum^\infty_{k=0}x^k, \mid x\mid \lt 1} k = 0 ∑ ∞ x k , ∣ x ∣< 1
1 1 − x \displaystyle{\frac{1}{1-x}} 1 − x 1
∑ k = 1 ∞ x k , ∣ x ∣ < 1 \displaystyle{\sum^\infty_{k=1}x^k, \mid x\mid \lt 1} k = 1 ∑ ∞ x k , ∣ x ∣< 1
1 ( 1 − x ) 2 \displaystyle{\frac{1}{(1-x)^2}} ( 1 − x ) 2 1
Double Sums
Sometimes we want to sum a matrix of numbers
To do this we use a double sum
( a 11 a 12 ⋯ a 1 n ⋮ ⋮ ⋯ ⋮ a n 1 a n 2 ⋯ a n n ) ∑ k , l = 1 n a k l = ∑ k = 1 n ∑ l = 1 n a k l So first sum all l terms then sum all k terms Ex ∑ k = 1 3 ∑ l = 2 4 ( k + 1 ) l 2 = ∑ k = 1 3 { ( k + 1 ) 4 + ( k + 1 ) 9 + ( k + 1 ) 16 } = ∑ k = 1 3 29 ( k + 1 ) = 29 ( ∑ k = 1 3 ( k + 1 ) ) = 29 [ 2 + 3 + 4 ] = 29 × 9 = 261
\begin{pmatrix}
a_{11} &a_{12} &\cdots& &a_{1n} \\
\vdots &\vdots &\cdots& &\vdots \\
a_{n1} &a_{n2} &\cdots& &a_{nn} \\
\end{pmatrix}\\
\newline
\sum^n_{k,l=1}a_{kl}\quad =\quad \sum^n_{k=1}\sum^n_{l=1}a_{kl}
\newline
\newline
\color{violet}{\text{So first sum all $l$ terms then sum all $k$ terms}}\\
\begin{aligned}
& \text { Ex } \quad \sum_{k=1}^3 \sum_{l=2}^4(k+1) l^2 \\
&=\sum_{k=1}^3\{(k+1) 4+(k+1) 9+(k+1) 16\} \\
&=\sum_{k=1}^3 29(k+1)=29\left(\sum_{k=1}^3(k+1)\right) \\
&=29[2+3+4]=29 \times 9=261
\end{aligned}
⎝ ⎛ a 11 ⋮ a n 1 a 12 ⋮ a n 2 ⋯ ⋯ ⋯ a 1 n ⋮ a nn ⎠ ⎞ k , l = 1 ∑ n a k l = k = 1 ∑ n l = 1 ∑ n a k l So first sum all l terms then sum all k terms Ex k = 1 ∑ 3 l = 2 ∑ 4 ( k + 1 ) l 2 = k = 1 ∑ 3 {( k + 1 ) 4 + ( k + 1 ) 9 + ( k + 1 ) 16 } = k = 1 ∑ 3 29 ( k + 1 ) = 29 ( k = 1 ∑ 3 ( k + 1 ) ) = 29 [ 2 + 3 + 4 ] = 29 × 9 = 261 Note
Sometimes we don't explicitly state s or sometimes S S S is a contiguous set of integers, for example S = \set 1 , 3 , 27 , 413 , 999 , 1 0 6 , 1 0 2 5 S=\set{1,3,27,413,999,10^6,10^25} S = \set 1 , 3 , 27 , 413 , 999 , 1 0 6 , 1 0 2 5
We can still us summation
∑ k ∈ S a k o r ∑ k ∈ S f ( k )
\displaystyle\sum_{k\in S}a_k\quad or\quad \sum_{k\in S}f(k)
k ∈ S ∑ a k or k ∈ S ∑ f ( k ) Special Finite Arithmetic Sequence
(1) ∑ k = 1 n k = n ( n + 1 ) 2 = 1 + 2 + ⋯ + n \displaystyle\sum_{k=1}^{n} k=\frac{n(n+1)}{2}=1+2+\cdots+n k = 1 ∑ n k = 2 n ( n + 1 ) = 1 + 2 + ⋯ + n
Proof: ∑ k = 0 n ( a + d k ) \sum_{k=0}^{n}(a+dk) ∑ k = 0 n ( a + d k )
prf:theorem Finite Arithmetic Sequences in General
$$
A_n = \sum^n_{k=1}(a+dk) = \frac{(n+1)(2a+nd)}{2}
$$
----------
{bdg-secondary}`Proof`
$$
A_n &=\sum^n_{k=1}(a+dk)\\
&=\sum^n_{k=1}a + \sum^n_{k=1}dk\\
&=a\sum^n_{k=1}1 + d\sum^n_{k=1}k\\
&=(n+1)a + d\sum^n_{k=1}k\\
&=(n+1)a + d\left(\frac{2(n+1)}{2}\right)\\
&=\frac{(n+1)(2a+nd)}{2}
$$
```{note}
We will prove $\displaystyle \sum^n_{k=1}k = 1+2+3+\cdots+n = \frac{2(n+1)}{2}$ later
```
Proof: ∑ k = 1 n k \sum_{k=1}^{n}k ∑ k = 1 n k
This is a Arithmetic Sequence
S=\text{Let }\sum^n_{k=1} &= 1+2+3+\cdots+(n-1)+n\\
\text{(backwards) }S &= n + (n-1) + (n-2) + \cdots + 2 + 1\\
\newline
\therefore \quad 2 S &=(n+1)+(n+1)+\cdots+(n+1)(n \text { terms }) \\
& =n(n+1) \\
\newline
\therefore\ \quad S &=\frac{n(n+1)}{2}
(2) ∑ k = 1 n k 2 = n ( n + 1 ) ( 2 n + 1 ) 6 = 1 + 4 + 9 + ⋯ + n 2 \displaystyle\sum_{k=1}^{n} k^{2}=\frac{n(n+1)(2 n+1)}{6}=1+4+9+\cdots+n^{2} k = 1 ∑ n k 2 = 6 n ( n + 1 ) ( 2 n + 1 ) = 1 + 4 + 9 + ⋯ + n 2
(3) ∑ k = 1 n k 3 = [ n ( n + 1 ) 2 ] 2 = 1 + 8 + 27 + ⋯ + n 3 \displaystyle\sum_{k=1}^{n} k^{3}=\left[\frac{n(n+1)}{2}\right]^{2}=1+8+27+\cdots+n^{3} k = 1 ∑ n k 3 = [ 2 n ( n + 1 ) ] 2 = 1 + 8 + 27 + ⋯ + n 3
bdg-danger Later We will prove (2) & (3) using principle of mathematical induction
Infinite Series
Infinite series are important in many branches of mathematics, especially mathematical analysis
An infinite series is a summation of an infinite number of terms
Actually the sum of an infinite number of terms is not defined
However we can talk about these infinite sums in the context of wether or not they converge to a sum by looking at the sequence of partial sums
Let { a n } n = 0 + ∞ \left\{a_{n}\right\}_{n=0}^{+\infty} { a n } n = 0 + ∞ be an infinite sequence of real numbers.
Let { S n } n = 0 + ∞ \left\{S_{n}\right\}_{n=0}^{+\infty} { S n } n = 0 + ∞ be the sequence of partial sums of { a n } n = 0 + ∞ \left\{a_{n}\right\}_{n=0}^{+\infty} { a n } n = 0 + ∞ ,
s n = ∑ k = 0 n a k = a 0 + a 1 + ⋯ + a n
s_{n}=\sum_{k=0}^{n} a_{k}=a_{0}+a_{1}+\cdots+a_{n}
s n = k = 0 ∑ n a k = a 0 + a 1 + ⋯ + a n Before we go any further we must talk about the limit of a sequence
Let { S n } n = 0 + ∞ \left\{S_{n}\right\}_{n=0}^{+\infty} { S n } n = 0 + ∞ be a sequence of real numbers (infinite).
We say { S n } n = 0 + ∞ \left\{S_{n}\right\}_{n=0}^{+\infty} { S n } n = 0 + ∞ converges to L L L
or
lim n → + ∞ S n = L iff ∀ ε > 0 , ∃ N ( ε ) ∈ Z + such that ∣ S n − L ∣ < ε , ∀ n ⩾ N
\begin{aligned}
& \displaystyle\lim _{n \rightarrow+\infty} S_{n}=L \quad \text { iff }\\
\newline
& \forall \varepsilon>0,\quad\exists N(\varepsilon) \in \mathbb{Z}^{+} \text { such that}\\
& \left|S_{n}-L\right|<\varepsilon,\quad \forall n \geqslant N
\end{aligned}
n → + ∞ lim S n = L iff ∀ ε > 0 , ∃ N ( ε ) ∈ Z + such that ∣ S n − L ∣ < ε , ∀ n ⩾ N What this means is that the larger that n n n gets the chosen s n s_{n} s n gets to L L L
and we say that S n → L S_{n} \rightarrow L S n → L as x → + ∞ x \rightarrow+\infty x → + ∞
If there is no number L L L such that S x → L S_{x} \rightarrow L S x → L as n → + ∞ n \rightarrow+\infty n → + ∞ we say that the sequence { S n } n = 0 + ∞ \left\{S_{n}\right\}_{n=0}^{+\infty} { S n } n = 0 + ∞ diverges
( 12 ) (12) ( 12 )
Two important limits
(1) lim n → + ∞ x n = 0 \displaystyle\lim _{n \rightarrow+\infty} x^{n}=0 n → + ∞ lim x n = 0 if ∣ x ∣ < 1 |x|<1 ∣ x ∣ < 1
(2) lim n → + ∞ 1 n = 0 \displaystyle\lim _{n \rightarrow+\infty} \frac{1}{n}=0 n → + ∞ lim n 1 = 0
We have already discussed (2) before with the calculator if n becomes large enough the answer converges to 0
We prove (1) using Bernoulli's inequality
1 + n h ⩽ ( 1 + h ) n , ∀ n = 0 , 1 , 2 , … , h > − 1
\begin{gathered}
1+nh \leqslant(1+h)^{n},\quad \forall n=0,1,2, \ldots,\quad h>-1
\end{gathered}
1 + nh ⩽ ( 1 + h ) n , ∀ n = 0 , 1 , 2 , … , h > − 1 We will see a proof of this inequality later by proof by mathematical induction
lim n → + ∞ 1 n = 0 \displaystyle\lim _{n \rightarrow+\infty} \frac{1}{n}=0 n → + ∞ lim n 1 = 0 if ∣ x ∣ < 1 |x|<1 ∣ x ∣ < 1
Proof by Cases
case (i) 0 < x < 1 0<x<1 0 < x < 1 .
Write x = 1 1 + h , h > 0 x=\displaystyle\frac{1}{1+h}, h>0 x = 1 + h 1 , h > 0
then x n = 1 ( 1 + h ) n ⩽ 1 1 + x h → 1 a > 1 b x^{n}=\displaystyle\frac{1}{(1+h)^{n}} \leqslant \frac{1}{1+x h} \quad \begin{array}{ll} & \rightarrow \frac{1}{a}>\frac{1}{b}\end{array} x n = ( 1 + h ) n 1 ⩽ 1 + x h 1 → a 1 > b 1
< 1 n h
<\frac{1}{n h}
< nh 1 Thus ∣ x n − 0 ∣ = ∣ x n ∣ = 1 ( 1 + h ) n < 1 n h < ε \left|x^{n}-0\right|=\left|x^{n}\right|=\frac{1}{(1+h)^{n}}<\frac{1}{n h}<\varepsilon ∣ x n − 0 ∣ = ∣ x n ∣ = ( 1 + h ) n 1 < nh 1 < ε if n h > 1 ε n h>\frac{1}{\varepsilon} nh > ε 1 , ie x > 1 h ε x>\frac{1}{h \varepsilon} x > h ε 1 oR x ⩾ ⌈ 1 h ε ⌉ x \geqslant\left\lceil\frac{1}{h \varepsilon}\right\rceil x ⩾ ⌈ h ε 1 ⌉ (13)
for any ε > 0 \varepsilon>0 ε > 0 .
Thus ∀ ε > 0 , x x ∣ < ε \forall \varepsilon>0, \quad x^{x} \mid<\varepsilon \quad ∀ ε > 0 , x x ∣< ε whenever
n ⩾ ⌈ 1 n ε ⌉ , x = 1 1 + h
n \geqslant\left\lceil\frac{1}{n \varepsilon}\right\rceil \quad, x=\frac{1}{1+h}
n ⩾ ⌈ n ε 1 ⌉ , x = 1 + h 1 case (ii) x = 0 , x n = 0 → 0 x=0, x^{n}=0 \rightarrow 0 x = 0 , x n = 0 → 0 as x → + ∞ x \rightarrow+\infty x → + ∞
case (iii) − 1 < x < 0 -1<x<0 − 1 < x < 0
then 0 < − x < 1 0<-x<1 0 < − x < 1
and − x = 1 1 + h , h > 0 -x=\frac{1}{1+h}, h>0 − x = 1 + h 1 , h > 0
so
∣ x n − 0 ∣ = ∣ x x ∣ = 1 ( 1 + h ) n < 1 x h \left|x^{n}-0\right|=\left|x^{x}\right|=\frac{1}{(1+h)^{n}}<\frac{1}{x h} ∣ x n − 0 ∣ = ∣ x x ∣ = ( 1 + h ) n 1 < x h 1 as before
Exevise Show ( 1 ) (1) ( 1 ) is really "if" by showing ∣ x ∣ ⩾ 1 ⇒ lim n → + ∞ x n ≠ 0 |x| \geqslant 1 \Rightarrow \lim _{n \rightarrow+\infty} x^{n} \neq 0 ∣ x ∣ ⩾ 1 ⇒ lim n → + ∞ x n = 0
Returning to infinite series,
We say ∑ n = 0 + ∞ a n \sum_{n=0}^{+\infty} a_{n} ∑ n = 0 + ∞ a n converges to L L L
and wite ∑ n = 0 + ∞ a n = L \sum_{n=0}^{+\infty} a_{n}=L ∑ n = 0 + ∞ a n = L if
lim n → + ∞ S n = lim n → + ∞ ( ∑ k = 0 n a k ) = L
\lim _{n \rightarrow+\infty} S_{n}=\lim _{n \rightarrow+\infty}\left(\sum_{k=0}^{n} a_{k}\right)=L
n → + ∞ lim S n = n → + ∞ lim ( k = 0 ∑ n a k ) = L (14)
Thus an infinite series converges the sequence of partial sums converges to a limit.
If ∑ n = 0 + ∞ a n \sum_{n=0}^{+\infty} a_{n} ∑ n = 0 + ∞ a n is not convergent,
ie, lim n → + ∞ S n \lim _{n \rightarrow+\infty} S_{n} lim n → + ∞ S n does not exist,
we say ∑ n = 0 + ∞ a n \sum_{n=0}^{+\infty} a_{n} ∑ n = 0 + ∞ a n is divergent.
The Infinite Geometric Series
∑ k = 0 + ∞ a r k is convergent if and only if ∣ r ∣ < 1
\sum_{k=0}^{+\infty} a r^{k} \quad \text { is convergent if and only if }|r|<1
k = 0 ∑ + ∞ a r k is convergent if and only if ∣ r ∣ < 1 Since G n = ∑ k = 0 n a r k = a ( r n + 1 − 1 ) r − 1 G_{n}=\displaystyle\sum_{k=0}^{n} a r^{k}=\frac{a\left(r^{n+1}-1\right)}{r-1} G n = k = 0 ∑ n a r k = r − 1 a ( r n + 1 − 1 )
If ∣ r ∣ < 1 |r|<1 ∣ r ∣ < 1 , then lim n → + ∞ G n = lim n → + ∞ a ( r n + 1 − 1 ) r − 1 \displaystyle\lim _{n \rightarrow+\infty} G_{n}=\lim _{n \rightarrow+\infty} \frac{a\left(r^{n+1}-1\right)}{r-1} n → + ∞ lim G n = n → + ∞ lim r − 1 a ( r n + 1 − 1 )
= a ( 0 − 1 ) r − 1 = a 1 − r
\begin{aligned}
& =\frac{a(0-1)}{r-1} \\
& =\frac{a}{1-r}
\end{aligned}
= r − 1 a ( 0 − 1 ) = 1 − r a Thus for ∣ r ∣ < 1 , ∑ k = 0 + ∞ a r k = a 1 − r \displaystyle|r|<1, \sum_{k=0}^{+\infty} a r^{k}=\frac{a}{1-r} ∣ r ∣ < 1 , k = 0 ∑ + ∞ a r k = 1 − r a
Exercise: 0.999 ⋯ = 1 0.999 \cdots=1 0.999 ⋯ = 1
Exercise use this result to show 0.999 ⋯ = 1 0.999 \cdots=1 0.999 ⋯ = 1
0.9999 ⋯ = 9 10 + 9 100 + ⋯ = ∑ k = 1 ∞ 9 1 0 k = 9 ( ∑ k = 1 ∞ ( 1 10 ) k ) = 9 ( 1 10 + 1 1 0 2 + ⋯ + 1 1 0 n + 1 1 0 n + 1 + ⋯ ) = 9 10 ( 1 + 1 10 + 1 1 0 2 + ⋯ ) = 9 10 ∑ k = 0 ∞ ( 1 10 ) k = 9 10 1 1 − 1 10 = 9 10 ⋅ 1 ( 9 10 ) = 1
\begin{aligned}
0.9999 \cdots = \frac{9}{10} + \frac{9}{100} + \cdots & =\sum_{k=1}^{\infty} \frac{9}{10^{k}} \\
& =9\left(\sum_{k=1}^{\infty}\left(\frac{1}{10}\right)^{k}\right) \\
& =9\left(\frac{1}{10}+\frac{1}{10^{2}}+\cdots+\frac{1}{10^{n}}+\frac{1}{10^{n+1}}+\cdots\right) \\
& =\frac{9}{10}\left(1+\frac{1}{10}+\frac{1}{10^{2}}+\cdots\right) \\
& =\frac{9}{10} \sum_{k=0}^{\infty}\left(\frac{1}{10}\right)^{k}=\frac{9}{10} \frac{1}{1-\frac{1}{10}} \\
& =\frac{9}{10} \cdot \frac{1}{\left(\frac{9}{10}\right)}=1
\end{aligned}
0.9999 ⋯ = 10 9 + 100 9 + ⋯ = k = 1 ∑ ∞ 1 0 k 9 = 9 ( k = 1 ∑ ∞ ( 10 1 ) k ) = 9 ( 10 1 + 1 0 2 1 + ⋯ + 1 0 n 1 + 1 0 n + 1 1 + ⋯ ) = 10 9 ( 1 + 10 1 + 1 0 2 1 + ⋯ ) = 10 9 k = 0 ∑ ∞ ( 10 1 ) k = 10 9 1 − 10 1 1 = 10 9 ⋅ ( 10 9 ) 1 = 1 We have shown only the "If" part of own statement.
To prove the "only if " part, we note
for r = 1 , G n = a ( x + 1 ) → + ∞ r=1, G_{n}=a(x+1) \rightarrow+\infty r = 1 , G n = a ( x + 1 ) → + ∞ as n → + ∞ n \rightarrow+\infty n → + ∞
so { G n } n = 0 + ∞ \left\{G_{n}\right\}_{n=0}^{+\infty} { G n } n = 0 + ∞ does not have a limit (it diverges to + ∞ +\infty + ∞ ) and ∑ k = 0 + ∞ a ( 1 ) k \sum_{k=0}^{+\infty} a(1)^{k} ∑ k = 0 + ∞ a ( 1 ) k is divergent,
If ∣ r ∣ > 1 |r|>1 ∣ r ∣ > 1 , one can show that lim n → + ∞ ( r n + 1 ) \lim _{n \rightarrow+\infty}\left(r^{n+1}\right) lim n → + ∞ ( r n + 1 ) does not exist since if r > 1 r>1 r > 1 , these terms get larger and larger positively, while if r < − 1 , r n + 1 r<-1, r^{n+1} r < − 1 , r n + 1 gets larger and larger in absolute value and it switches from positive to negative and so cant have a limit
EXERCISE: What happens when r = − 1 r=-1 r = − 1 ?
Principle of Mathematical Induction
Consider a formal sequence of propositional functions { P ( n ) } n = 1 + ∞ \{P(n)\}_{n=1}^{+\infty} { P ( n ) } n = 1 + ∞ .
We want to be able to prove that the proposition ∀ n P ( n ) \forall n P(n) ∀ n P ( n ) is True where the universe of discourse for the universal quantifier, ∀ \forall ∀ , is Z + \mathbb{Z}^{+} Z + .
As some examples of such a proposition we have the 3 summation formulae from before,
∑ k = 1 n k = n ( n + 1 ) 2 , ∀ n + Z + \sum_{k=1}^{n} k=\frac{n(n+1)}{2}, \forall n+\mathbb{Z}^{+} k = 1 ∑ n k = 2 n ( n + 1 ) , ∀ n + Z +
¶
∑ k = 1 n k 2 = n ( n + 1 ) ( 2 n + 1 ) 6 , ∀ n ∈ Z + \sum_{k=1}^{n} k^{2}=\frac{n(n+1)(2 n+1)}{6}, \forall n \in \mathbb{Z}^{+} k = 1 ∑ n k 2 = 6 n ( n + 1 ) ( 2 n + 1 ) , ∀ n ∈ Z +
¶
∑ k = 1 n k 3 = [ n ( n + 1 ) 2 ] 2 , ∀ n ∈ Z + \sum_{k=1}^{n} k^{3}=\left[\frac{n(n+1)}{2}\right]^{2}, \forall n \in \mathbb{Z}^{+} k = 1 ∑ n k 3 = [ 2 n ( n + 1 ) ] 2 , ∀ n ∈ Z +
¶
We prove such universally quantified propositions using the principle of mathematical induction
Steps
principle of mathematical induction has 2 steps.
Step 1 Basis step; prove P ( 1 ) P(1) P ( 1 ) is true.
Step 2 Inductive step; prove that the proposition
∀ k ( P ( k ) → P ( k + 1 ) ) ( k ≥ 1 ) \forall k(P(k) \rightarrow P(k+1)) \quad(k \geq 1) ∀ k ( P ( k ) → P ( k + 1 )) ( k ≥ 1 ) is true
We will prove the validity of PMI. later
For now consider some examples. At the same time we will be proving useful and important results
Prove statement 1
Exercise Prove statement eq induction-1 above. [ Note, we already gave a direct proof by showing P ( n ) is T , for all n ] \left[\begin{array}{c}\text { Note, we already gave a direct proof } \\ \text { by showing } P(n) \text { is } T \text {, for all } n\end{array}\right] [ Note, we already gave a direct proof by showing P ( n ) is T , for all n ]
Let P ( n ) P(n) P ( n ) be the statement
∑ k = 1 n k = n ( n + 1 ) 2 = f ( n )
\sum_{k=1}^{n} k=\frac{n(n+1)}{2}=f(n)
k = 1 ∑ n k = 2 n ( n + 1 ) = f ( n ) Basis Step
P ( 1 ) : ∑ k = 1 1 k = 1 , f ( 1 ) = 1 ( 1 + 1 ) 2 = 1 \displaystyle P(1): \sum_{k=1}^{1} k=1, f(1)=\frac{1(1+1)}{2}=1 P ( 1 ) : k = 1 ∑ 1 k = 1 , f ( 1 ) = 2 1 ( 1 + 1 ) = 1
∴ P ( 1 ) \therefore P(1) ∴ P ( 1 ) is true
Inductive step
assume P k ( k ) P_{k}(k) P k ( k ) is tue, k ∈ Z + ( k ⩾ 1 ) k \in \mathbb{Z}^{+}(k \geqslant 1) k ∈ Z + ( k ⩾ 1 )
That is ∑ l = 1 k l = k ( k + 1 ) 2 = f ( k ) \displaystyle\sum_{l=1}^{k} l=\frac{k(k+1)}{2}=f(k) l = 1 ∑ k l = 2 k ( k + 1 ) = f ( k ) .
We show now that P ( k + 1 ) P(k+1) P ( k + 1 ) is true,
ie, ∑ k = 1 k + 1 l = f ( k + 1 ) = ( k + 1 ) ( k + 2 ) 2 \displaystyle\sum_{k=1}^{k+1} l=f(k+1) =\frac{(k+1)(k+2)}{2} k = 1 ∑ k + 1 l = f ( k + 1 ) = 2 ( k + 1 ) ( k + 2 )
But
∑ l = 1 k + 1 l = ∑ ℓ = 1 k l + ( k + 1 ) = k ⋅ ( k + 1 ) 2 + ( k + 1 ) , by hypothesis. = ( k + 1 ) ( k 2 + 1 ) = ( k + 1 ) ( k + 2 ) 2 = f ( k + 1 )
\begin{aligned}
\sum_{l=1}^{k+1} l&=\sum_{\ell=1}^{k} l+(k+1) \\
& =\frac{k\cdot (k+1)}{2}+(k+1), \text { by hypothesis. } \\
& =(k+1)\left(\frac{k}{2}+1\right) \\
& =\frac{(k+1)(k+2)}{2}=f(k+1)
\end{aligned}
l = 1 ∑ k + 1 l = ℓ = 1 ∑ k l + ( k + 1 ) = 2 k ⋅ ( k + 1 ) + ( k + 1 ) , by hypothesis. = ( k + 1 ) ( 2 k + 1 ) = 2 ( k + 1 ) ( k + 2 ) = f ( k + 1 ) Thus P ( k ) → P ( k + 1 ) , ∀ k ∈ Z + P(k) \rightarrow P(k+1), \forall k \in \mathbb{Z}^{+} P ( k ) → P ( k + 1 ) , ∀ k ∈ Z +
Hence by P M I , ∑ k = 1 n k = n ( n + 1 ) 2 , ∀ n ∈ Z + \displaystyle P M I, \sum_{k=1}^{n} k=\frac{n(n+1)}{2}, \forall n \in \mathbb{Z}^{+} PM I , k = 1 ∑ n k = 2 n ( n + 1 ) , ∀ n ∈ Z +
Prove Statement 2
Prove eq induction-2 above: ∑ k = 1 n k 2 = n ( n + 1 ) ( 2 n + 1 ) 6 , ∀ n ∈ Z \displaystyle\sum_{k=1}^{n} k^{2}=\frac{n(n+1)(2 n+1)}{6}, \forall n \in \mathbb{Z} k = 1 ∑ n k 2 = 6 n ( n + 1 ) ( 2 n + 1 ) , ∀ n ∈ Z = f ( x ) =f(x) = f ( x )
Basis Step
n = 1. ∑ k = 1 k 2 = 1 ; f ( 1 ) = 1 ( 2 ) ( 3 ) 6 = 1
n=1 . \quad \sum_{k=1} k^{2}=1 ; f(1)=\frac{1(2)(3)}{6}=1
n = 1. k = 1 ∑ k 2 = 1 ; f ( 1 ) = 6 1 ( 2 ) ( 3 ) = 1 Thus P ( 1 ) P(1) P ( 1 ) is true
Inductive Step
Assume P ( k ) P(k) P ( k ) is true, k ∈ Z + ( k ⩾ 1 ) k \in \mathbb{Z}^{+}(k \geqslant 1) k ∈ Z + ( k ⩾ 1 )
T h e n ∑ l = 1 k + 1 l 2 = ∑ l = 1 k l 2 + ( k + 1 ) 2 = k ( k + 1 ) ( 2 k + 1 ) 6 + ( k + 1 ) 2 , by hypothesis = ( k + 1 ) [ k ( 2 k + 1 ) 6 + k + 1 ] = ( k + 1 ) [ 2 k 2 + k + 6 ( k + 1 ) 6 ] = ( k + 1 ) [ 2 k 2 + 7 k + 6 6 ] = ( k + 1 ) 6 [ 2 k 2 + 4 k + 3 k + 6 ] = ( k + 1 ) 6 [ 2 k ( k + 2 ) + 3 ( k + 2 ) ] = ( k + 1 ) ( k + 2 ) ( 2 k + 3 ) 6 = f ( k + 1 )
\begin{aligned}
Then\quad\sum_{l=1}^{k+1} l^{2}&=\sum_{l=1}^{k} l^{2}+(k+1)^{2}\\
\newline
& =\frac{k(k+1)(2k+1)}{6}+(k+1)^{2} \text {, by hypothesis} \\
\newline
& =(k+1)\left[\frac{k(2 k+1)}{6}+k+1\right] \\
\newline
& =(k+1)\left[\frac{2k^{2}+k+6(k+1)}{6}\right] \\
\newline
& =(k+1)\left[\frac{2k^{2}+7k+6}{6}\right] \\
\newline
& =\frac{(k+1)}{6}\left[2k^{2}+4k + 3k+6\right] \\
\newline
& =\frac{(k+1)}{6}[2 k(k+2)+3(k+2)] \\
\newline
& =\frac{(k+1)(k+2)(2k+3)}{6}=f(k+1)
\end{aligned}
T h e n l = 1 ∑ k + 1 l 2 = l = 1 ∑ k l 2 + ( k + 1 ) 2 = 6 k ( k + 1 ) ( 2 k + 1 ) + ( k + 1 ) 2 , by hypothesis = ( k + 1 ) [ 6 k ( 2 k + 1 ) + k + 1 ] = ( k + 1 ) [ 6 2 k 2 + k + 6 ( k + 1 ) ] = ( k + 1 ) [ 6 2 k 2 + 7 k + 6 ] = 6 ( k + 1 ) [ 2 k 2 + 4 k + 3 k + 6 ] = 6 ( k + 1 ) [ 2 k ( k + 2 ) + 3 ( k + 2 )] = 6 ( k + 1 ) ( k + 2 ) ( 2 k + 3 ) = f ( k + 1 ) Thus ∀ k ∈ Z + , P ( k ) → P ( k + 1 ) \forall k \in \mathbb{Z}^{+},\quad P(k) \rightarrow P(k+1) ∀ k ∈ Z + , P ( k ) → P ( k + 1 ) is true
and by the principle of mathematical induction
P ( n ) P(n) P ( n ) is true, ∀ n + Z + \forall n+\mathbb{Z}^{+} ∀ n + Z +
Common Errors
Note
A common error in proofs using principle of mathematical induction that lead to an invalid conclusion occurs in the inductive step when we prove P ( k ) → P ( k + 1 ) P(k) \rightarrow P(k+1) P ( k ) → P ( k + 1 ) is true for k = 2 , 3 , 4 , … k=2,3,4, \ldots k = 2 , 3 , 4 , … , and not for k = 1 k=1 k = 1 . Then there is no connection between the basis step and the inductive step. This will occur when we have to assume k > 1 k>1 k > 1 in a order to prove P ( k ) → P ( k + 1 ) P(k) \rightarrow P(k+1) P ( k ) → P ( k + 1 ) If P ( 2 ) P(2) P ( 2 ) is false, then we cant conclude ∀ n P ( n ) \forall n P(n) ∀ n P ( n )
We may use P M I P M I PM I to prove ∀ n ⩾ n 0 , P ( n ) \forall n \geqslant n_{0}, P(n) ∀ n ⩾ n 0 , P ( n ) is true where n 0 > 1 n_{0}>1 n 0 > 1 by changing the basis step to P ( n 0 ) P\left(n_{0}\right) P ( n 0 ) is True, and the inductive step to ∀ k ⩾ n 0 , P ( k ) → P ( k + 1 ) \forall k \geqslant n_{0}, P(k) \rightarrow P(k+1) ∀ k ⩾ n 0 , P ( k ) → P ( k + 1 )
The Harmonic Progression
Recall the Harmonic Progression { a n } n = 1 ∞ \left\{a_{n}\right\}_{n=1}^{\infty} { a n } n = 1 ∞ where a n = 1 n a_{n}=\frac{1}{n} a n = n 1 .
Even though,
lim n → + ∞ a n = lim n → + ∞ 1 n = 0 ,
\lim _{n \rightarrow+\infty} a_{n}=\lim _{n \rightarrow+\infty} \frac{1}{n}=0 \text {, }
n → + ∞ lim a n = n → + ∞ lim n 1 = 0 , the Harmonic series ∑ n = 1 + ∞ 1 n = 1 + 1 2 + 1 3 + ⋯ + 1 n + ⋯ \displaystyle\sum_{n=1}^{+\infty} \frac{1}{n}=1+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{n}+\cdots n = 1 ∑ + ∞ n 1 = 1 + 2 1 + 3 1 + ⋯ + n 1 + ⋯ is divergent
The smaller and smaller bit added infinitely often add up to + ∞ +\infty + ∞ !
We will use the principle of mathematical induction to help prove this fact
Lemma Let $H_{n}=\sum_{k=1}^{n} \frac{1}{k}$.
Then $H_{2^n} \geqslant 1+\frac{n}{2}=f(x), \forall n \in \mathbb{Z}^{+}$
bdg-secondary Proof
Basis step
n = 1 H 2 1 = 1 + 1 2 = f ( 1 ) ∴ H 2 1 ⩾ f ( 1 )
\begin{aligned}
& n=1 \\
& H_{2^{1}}=1+\frac{1}{2}=f(1) \quad \therefore H_{2^1} \geqslant f(1)
\end{aligned}
n = 1 H 2 1 = 1 + 2 1 = f ( 1 ) ∴ H 2 1 ⩾ f ( 1 ) Inductive Step
assume H 2 k ⩾ 1 + k 2 , ∀ k ∈ Z + H_{2^{k}} \geqslant 1+\frac{k}{2}, \forall k \in \mathbb{Z}^{+} H 2 k ⩾ 1 + 2 k , ∀ k ∈ Z +
Then
H 2 k + 1 = ∑ k = 1 2 k + 1 1 k = ∑ r = 1 2 k 1 r + ∑ k = 2 k + 1 2 k + 1 1 r ⩾ 1 + k 2 + 1 2 k + 1 + 1 2 k + 2 + ⋯ + 1 2 k + 1 = 1 + k 2 + 1 2 k + 1 + 1 2 k + 2 + ⋯ + 1 2 k + 2 k
\begin{aligned}
H_{2^{k+1}} & =\sum_{k=1}^{2^{k+1}} \frac{1}{k}=\sum_{r=1}^{2^{k}} \frac{1}{r}+\sum_{k=2^{k}+1}^{2^{k+1}} \frac{1}{r} \\
& \geqslant 1+\frac{k}{2}+\frac{1}{2^{k}+1}+\frac{1}{2^{k}+2}+\cdots+\frac{1}{2^{k+1}} \\
& =1+\frac{k}{2}+\frac{1}{2^{k}+1}+\frac{1}{2^{k}+2}+\cdots+\frac{1}{2^{k}+2^{k}}
\end{aligned}
H 2 k + 1 = k = 1 ∑ 2 k + 1 k 1 = r = 1 ∑ 2 k r 1 + k = 2 k + 1 ∑ 2 k + 1 r 1 ⩾ 1 + 2 k + 2 k + 1 1 + 2 k + 2 1 + ⋯ + 2 k + 1 1 = 1 + 2 k + 2 k + 1 1 + 2 k + 2 1 + ⋯ + 2 k + 2 k 1 ⩾ 1 + k 2 + { 1 2 k + 2 k + ⋯ + 2 k terms 2 k + 2 k } ( make the bottom bigger fraction get smaller ) = 1 + k 2 + 2 k ⋅ 1 2 k + 1 = 1 + k 2 + 1 2 = 1 + k + 1 2 = f ( k + 1 )
\begin{aligned}
& \geqslant 1+\frac{k}{2}+\left\{\frac{1}{2^{k}+2^{k}}+\cdots+\frac{2^{k} \text { terms }}{2^{k}+2^{k}}\right\} \quad\left(\begin{array}{l}
\text { make the } \\
\text { bottom bigger } \\
\text { fraction get } \\
\text { smaller }
\end{array}\right) \\
& =1+\frac{k}{2}+2^{k} \cdot \frac{1}{2^{k+1}}=1+\frac{k}{2}+\frac{1}{2}=1+\frac{k+1}{2}=f(k+1)
\end{aligned}
⩾ 1 + 2 k + { 2 k + 2 k 1 + ⋯ + 2 k + 2 k 2 k terms } ⎝ ⎛ make the bottom bigger fraction get smaller ⎠ ⎞ = 1 + 2 k + 2 k ⋅ 2 k + 1 1 = 1 + 2 k + 2 1 = 1 + 2 k + 1 = f ( k + 1 ) Thus by P,M.1. H 2 n ⩾ 1 + n 2 , ∀ n ∈ Z + H_{2} n \geqslant 1+\frac{n}{2}, \forall n \in \mathbb{Z}^{+} H 2 n ⩾ 1 + 2 n , ∀ n ∈ Z +
Now the sequence
{ H n } n = 1 ∞ \left\{H_{n}\right\}_{n=1}^{\infty} { H n } n = 1 ∞ is an "increasing" sequence
because H n + 1 = H n + 1 n + 1 > H n H_{n+1}=H_{n}+\frac{1}{n+1}>H_{n} H n + 1 = H n + n + 1 1 > H n .
Also the subsequence
{ H 2 n } x = 1 ∞ \left\{H_{2^{n}}\right\}_{x=1}^{\infty} { H 2 n } x = 1 ∞ clearly, in view of
the lemma, has
lim x → + ∞ H 2 x = + ∞
\lim _{x \rightarrow+\infty} H_{2 x}=+\infty
x → + ∞ lim H 2 x = + ∞ These two facts allow us to assent that
lim n → + ∞ H n = + ∞ and the
\lim _{n \rightarrow+\infty} H_{n}=+\infty \text { and the }
n → + ∞ lim H n = + ∞ and the hamonic series is divergent
Exerciser) Use PMI to prove that 3 / 2 2 n − 1 , ∀ x ∈ Z + 3 / 2^{2 n}-1, \forall x \in \mathbb{Z}^{+} 3/ 2 2 n − 1 , ∀ x ∈ Z +
Prove summation formula (3)
P351 #32 3 ∣ n 3 + 2 n ∀ n ⩾ 1 3 \mid n^{3}+2 n \quad \forall n \geqslant 1 3 ∣ n 3 + 2 n ∀ n ⩾ 1
23
P ( n ) : 3 ∣ n 3 + 2 n P(n): 3 \mid n^{3}+2 n \quad P ( n ) : 3 ∣ n 3 + 2 n R.T.P. ∀ n ⩾ 1 P ( n ) \quad \forall n \geqslant 1 P(n) ∀ n ⩾ 1 P ( n ) is the
Basis step
Let n = 1 , n 3 + 2 n = 1 + 2 = 3 + 3 / 3 n=1, n^{3}+2 n=1+2=3+3 / 3 n = 1 , n 3 + 2 n = 1 + 2 = 3 + 3/3
∴ P ( 1 ) \therefore P(1) ∴ P ( 1 ) is true
Inductive Step
want to show
∀ k ⩾ 1 P ( k ) → P ( k + 1 ) \forall k \geqslant 1 \quad P(k) \rightarrow P(k+1) \quad ∀ k ⩾ 1 P ( k ) → P ( k + 1 ) is tue
Assume 31 k 3 + 2 k 31 k^{3}+2 k 31 k 3 + 2 k ie assume P ( k ) P(k) P ( k ) is the
Then ( k 0 + 1 ) 3 + 2 ( k + 1 ) = k 3 + 3 k 2 + 3 k + 1 \left(k^{0}+1\right)^{3}+2(k+1)=k^{3}+3 k^{2}+3 k+1 ( k 0 + 1 ) 3 + 2 ( k + 1 ) = k 3 + 3 k 2 + 3 k + 1
= k 3 + 2 k + 3 k + 2 = k 3 + 2 k divisible by + 3 ( k 2 + k + 1 ) divisible by 3
\begin{aligned}
= & k^{3}+2 k+3 k+2 \\
= & \frac{k^{3}+2 k}{\text { divisible }_{\text {by }}}+\frac{3\left(k^{2}+k+1\right)}{\text { divisible by } 3}
\end{aligned}
= = k 3 + 2 k + 3 k + 2 divisible by k 3 + 2 k + divisible by 3 3 ( k 2 + k + 1 ) by hypothein
∴ P ( k + 1 ) \therefore P(k+1) ∴ P ( k + 1 ) is tue